package com.platform.modules.alg.alglib.hdu4902;

public class Hdu4902 {
    private int N = 100005;
    private int a[] = new int[N];
    private int maxs[] = new int[N << 2];
    private int lazy[] = new int[N << 2];
    private int n;
    private int m;

    public String output = "";

    // 最大公约数
    int gcd(int a, int b) {
        if (b == 0) return a;
        else return gcd(b, a % b);
    }

    // 上传
    void PushUp(int i) {
        maxs[i] = Math.max(maxs[i << 1], maxs[i << 1 | 1]);
    }

    // 下传
    void PushDown(int i) {
        if (lazy[i] != 0) {
            lazy[i << 1] = lazy[i << 1 | 1] = lazy[i];
            maxs[i << 1] = maxs[i << 1 | 1] = maxs[i];
            lazy[i] = 0;
        }
    }

    // 建线段树
    void build(int l, int r, int i) {
        if (l == r) {
            lazy[i] = a[l];
            maxs[i] = lazy[i];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, i << 1);
        build(mid + 1, r, i << 1 | 1);
        PushUp(i);
    }

    // 类型1更新
    void update1(int x, int L, int R, int l, int r, int i) {
        if (L <= l && r <= R) {
            lazy[i] = maxs[i] = x;
            return;
        }
        PushDown(i);
        int mid = (l + r) >> 1;
        if (L <= mid)
            update1(x, L, R, l, mid, i << 1);
        if (R > mid)
            update1(x, L, R, mid + 1, r, i << 1 | 1);
        PushUp(i);
    }

    // 类型2更新
    void update2(int x, int L, int R, int l, int r, int i) {
        if (maxs[i] <= x) return;
        if (lazy[i] != 0 && L <= l && r <= R) {
            lazy[i] = gcd(lazy[i], x);
            maxs[i] = lazy[i];
            return;
        }
        PushDown(i);
        int mid = (l + r) >> 1;
        if (L <= mid)
            update2(x, L, R, l, mid, i << 1);
        if (R > mid)
            update2(x, L, R, mid + 1, r, i << 1 | 1);
        PushUp(i);
    }

    void print(int l, int r, int i) {
        if (l == r) {
            output += lazy[i] + " ";
            return;
        }
        PushDown(i);
        int mid = (l + r) >> 1;
        print(l, mid, i << 1);
        print(mid + 1, r, i << 1 | 1);
    }

    public String cal(String input) {
        int l, r, opt;
        int x;
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        String[] nums = line[1].split(" ");
        for (int i = 1; i <= n; i++)
            a[i] = Integer.parseInt(nums[i - 1]);
        build(1, n, 1);
        m = Integer.parseInt(line[2]);
        int j = 0;
        while (m-- > 0) {
            String[] command = line[3 + j].split(" ");
            j++;
            opt = Integer.parseInt(command[0]);
            l = Integer.parseInt(command[1]);
            r = Integer.parseInt(command[2]);
            x = Integer.parseInt(command[3]);
            if (opt == 1) update1(x, l, r, 1, n, 1);
            else update2(x, l, r, 1, n, 1);
        }
        print(1, n, 1);
        return output;
    }
}
